package com.moyoutian.leetcode;

/**
 * 240. 搜索二维矩阵 II
 * <p>
 * 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
 * <p>
 * 每行的元素从左到右升序排列。
 * <p>
 * 每列的元素从上到下升序排列。
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
 * <p>
 * 输出：true
 * <p>
 * 示例 2：
 * <p>
 * <p>
 * 输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
 * <p>
 * 输出：false
 * <p>
 * <p>
 * 提示：
 * <p>
 * m == matrix.length
 * <p>
 * n == matrix[i].length
 * <p>
 * 1 <= n, m <= 300
 * <p>
 * -109 <= matrix[i][j] <= 109
 * <p>
 * 每行的所有元素从左到右升序排列
 * <p>
 * 每列的所有元素从上到下升序排列
 * <p>
 * -109 <= target <= 109
 */
public class Demo240 {


    public static void main(String[] args) {
/*        int[][] matrix = new int[][]{
                {1, 4, 7, 11, 15},
                {2, 5, 8, 12, 19},
                {3, 6, 9, 16, 22},
                {10, 13, 14, 17, 24},
                {18, 21, 23, 26, 30}};*/
        int[][] matrix = new int[][]{
                {1, 2, 3, 4, 5}};
/*        int[][] matrix = new int[][]{
                {1, 2, 3, 4, 5},
                {6, 7, 8, 9, 10},
                {11, 12, 13, 14, 15},
                {16, 17, 18, 19, 20},
                {21, 22, 23, 24, 25}};*/
        int target = 15;
        for (int x = 0; x < matrix.length; x++) {
            for (int y = 0; y < matrix[x].length; y++) {
                System.out.println(searchMatrix(matrix, matrix[x][y]));
            }
        }
    }

    /**
     * 对角线分割法
     *
     * @param matrix 二维数组
     * @param target 目标值
     * @return 目标值的下标
     */
    public static boolean searchMatrix(int[][] matrix, int target) {
        return searchMatrix(matrix, target, 0, matrix.length - 1, 0, matrix[0].length - 1);
    }

    /**
     * @param xBegin 横坐标开始
     * @param xEnd   横坐标结束
     * @param yBegin 宗坐标开始
     * @param yEnd   纵坐标结束
     */
    public static boolean searchMatrix(int[][] matrix, int target, int xBegin, int xEnd, int yBegin, int yEnd) {
        if (matrix[xBegin][yBegin] == target || target == matrix[xEnd][yEnd]) {
            return true;
        } else if (matrix[xBegin][yBegin] < target && target < matrix[xEnd][yEnd]) {
            // 横坐标中间点
            int xAvg;
            // 纵坐标中间点
            int yAvg;
            int xBegin_t = xBegin;
            int yBegin_t = yBegin;
            int xEnd_t = xEnd;
            int yEnd_t = yEnd;
            //起始点等于中间点，证明已斜线上没有可以查找的数据。当前点是最大的，一个满足小于目标点的点。证明左上角的方块部分可以不用排查。右下角方块也可以不用排查。
            while (xBegin_t < xEnd_t || yBegin_t < yEnd_t) {
                // 横坐标中间点
                xAvg = getAvgIndex(xBegin_t, xEnd_t);
                // 纵坐标中间点
                yAvg = getAvgIndex(yBegin_t, yEnd_t);
                if (matrix[xAvg][yAvg] > target) {
                    xEnd_t = xAvg - 1;
                    yEnd_t = yAvg - 1;
                } else if (matrix[xAvg][yAvg] < target) {
                    xBegin_t = xAvg;
                    yBegin_t = yAvg;
                } else if (matrix[xAvg][yAvg] == target) {
                    return true;
                }
            }
            boolean xFlag = false;
            boolean yFlag = false;
            if (xBegin_t < xEnd) {
                xFlag = searchMatrix(matrix, target, xBegin_t + 1, xEnd, yBegin, yBegin_t);
            }
            if (yBegin_t < yEnd) {
                yFlag = searchMatrix(matrix, target, xBegin, xBegin_t, yBegin_t + 1, yEnd);
            }
            return xFlag || yFlag;
        }
        return false;
    }

    /**
     * 获取中间结点下标
     *
     * @param begin 开始下标
     * @param end   结束下标
     */
    public static int getAvgIndex(int begin, int end) {
        //开始点，加上开始点到目标点中间的距离。
        return begin + (end - begin + 1) / 2;
    }


}
